package ercahshu

import "fmt"

func countNodes(root *TreeNode) int {
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}
		dfs(node.Right)
		dfs(node.Left)
		fmt.Println(node.Val)
	}
	dfs(root)
	return 0
}

func countNodes1(root *TreeNode) int {
	// 利用完全二叉树的特性进行处理
	if root == nil {
		return 0
	}
	leftH, rightH := 0, 0
	left, right := root.Left, root.Right
	for left != nil {
		leftH++
		left = left.Left
	}
	for right != nil {
		rightH++
		right = right.Right
	}
	if leftH == rightH {
		return 2<<leftH - 1
	}
	return countNodes1(root.Left) + countNodes1(root.Right) + 1
}
